package com.leetcode.二叉树.广度优先;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 给定一个非空二叉树的根节点 root , 以数组的形式返 回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
 * @author LZF
 *
 */
public class L637二叉树的层平均值 {
	/**
	 * 利用队列迭代实现，计算每一层的平均值，放入result即可
	 */
	public List<Double> averageOfLevels(TreeNode root) {
		List<Double> result = new ArrayList<Double>();
		Queue<TreeNode> que = new LinkedList<>();
		if(root != null) que.offer(root);
		while(!que.isEmpty()) {
			int len = que.size();//获取这一层的节点个数
			int i = len;//用于迭代的计数
			double sum = 0;//计算每一层的总和
			while(i > 0) {
				TreeNode node = que.poll();
				sum += node.val;
				if(node.left != null) que.offer(node.left);
				if(node.right != null) que.offer(node.right);
				i--;
			}
			result.add(sum / len);
		}
		return result;
    }
	
	//树的定义
	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
}
